1. Field of the Invention
The present invention relates to an automatic placement technology in the technological field such as a semiconductor integrated circuit technology, etc. in which the optimum performance of a composed system substantially depends on the placement of its parts and components.
2. Description of the Related Art
Normally, the shorter the interconnecting connection lines between the parts forming a semiconductor integrated circuit are, the higher the operation speed becomes and the smaller the consumption of electric power becomes. Therefore, in designing a semiconductor integrated circuit, great effort is made to minimize a total circuit connection line length.
The conventional methods of minimizing the total circuit connection line length are the simulated annealing (SA) method and the spectral method.
Conventional Technology: SA Method
First, the SA method is a conventional technology of applying the energy status analysis principle from the field of statistical thermodynamics to the minimization of the required total circuit connection line length. The SA method is disclosed by D. F. Wong, H. W. Leong, and C. L. Liu `Simulated Annealing for VLSI Design`, Kluwer Academic Publishers.
To shorten the total circuit connection line length, optional two parts i and j are normally selected from among all the parts forming the circuit. When the positions of the selected parts are exchanged for each other and if the exchange results in a shorter total circuit connection line length, then the exchange is actually made. These steps are repeated for the other circuit parts. However, since there are plural sets of connection lines connecting parts of a circuit, an exchange of some parts may shorten a connection line associated with those parts but may lengthen another connection line associated with other parts. Therefore, even if a total circuit connection line length appears shorter after sequentially repeating the selection and the exchange of the parts according to a predetermined rule, it still does not guarantee the shortest connection line length. This indicates that the minimization problem for a total circuit connection line length is an optimization problem in a multi-dimensional space, and it is probable that the above described result only refers to a local optimization solution.
The SA method provides the following solution to the above described circuit connection line-length minimization problem.
As for the transition of the energy of a substance, energy normally flows from a high toward a lower level. Therefore, when the energy of a substance is changing from one energy level E1 to another energy level E2, the transition occurs without fail if E1 is larger than E2 (E1&gt;E2). If E1 is smaller than E2 (E1&lt;E2), then the transition normally does not occur. However, if the temperature T of the substance is high, then the molecules forming the substance move actively. Therefore, there is a probability that the transition from E1 to E2 may occur even if E1 is smaller than E2 (E1&lt;E2). With the above described probability of transition, the energy of a substance may temporarily enter a local optimum solution state, but can leave this state and converge on the optimum balanced state (hill climbing method) in which the true minimum value for the current temperature T is obtained. If the energy of the substance converges to a balanced state at a specific temperature T and the temperature T drops a little, then the energy of the substance can converge to a new optimum balanced state in which a further minimum value for the new temperature T is obtained. Thus, if the temperature T gradually drops, the energy of a substance can converge to the optimum balanced state in which a true minimum value for an object temperature T can be obtained.
In statistical thermodynamics, when a first energy E1 is changing into a second energy E2 at a specific temperature T, the probability h that a transition may occur when E1&lt;E2 can be computed by the following equation (1). EQU h=exp (-(E2-E1))/(kT)) (1)
where k indicates a constant.
In the SA method, the solution to the transition problem of the above described energy status is applied to the circuit connection line length minimization problem.
That is, the concept of the temperature T is adopted in the SA method, and probable parts exchanging operations are repeated while the temperature T drops from a higher level to a lower level. To be more practical, the following operations are sequentially performed. Regardless of the actual temperature, the temperature T indicates a concept of an amount adopted to reduce in the proceeding of the processes the probability that an exchanging operation is actually performed when a total connection line length increases by exchanging parts.
Step 1 PA0 Step 2 PA0 Step 3 PA0 Step 4 PA0 Step 5 PA0 Step 6 PA0 Step 7
The initial temperature T is determined.
Two optional parts i and j are selected at random from among the parts forming the circuit.
The change d in total circuit connection line length after exchanging parts i and j is computed.
If d.ltoreq.0, the above described exchange is performed.
If d&gt;0, the probability h is computed by the following equation (2) based on the equation (1) above. EQU h=exp (-d/(kT)) (2)
A random number r is obtained within a range from 0 to 1. If r.ltoreq.h, the above described exchange is performed. If r&gt;h, the exchange is not performed.
After the processes in steps 2 through 5 are repeated a sufficient number of times, the temperature T is dropped a little, and the processes in steps 2 through 5 are repeated again a sufficient number of times.
When the temperature T drops to a predetermined level, the above described repetitive processes are stopped and the total connection line length at the stop point is output as a result.
Thus, when the temperature T is high in the SA method, there is a strong probability that parts are exchanged even if the exchanging operation requires a longer connection line length, because most of the positions of the parts in a circuit have not been optimized when processes have just started. There is also a strong possibility that the placement of the parts is set as the local optimum solution, and there should be the largest possible number of opportunities to set the placement of the parts away from the local optimum solution (hill climbing method). When the processes proceed and the temperature T becomes low, the placement of the parts in the circuit reaches an optimum status, and there is little possibility that the placement of the parts reaches the local optimum solution. Therefore, if the total connection line length becomes longer after exchanging parts, the system operates in such a way that the exchanging operation is not actually performed. Thus, in the SA method, the total connection line length can be optimally set to the minimum length.
However, since the above described SA method is based on a 2-parts exchange for a position change, a solution slowly improves, and the entire process requires a long time. Furthermore, a total connection line length should be computed in processes for exchanging all parts, and an operation should be performed using an exponent to compute probability in the exchanging processes for many parts. These processes also require a long time.
Therefore, the SA method requires an impractically long process time when there are a large number of parts in a circuit, such as in the latest semiconductor integrated circuits, etc.
Spectral Method
First, a one-dimensional placement is assumed for a simpler process. That is, it is assumed that the parts are arranged in a connection line.
In this case, the placement of each part can be expressed as one permutation, and can be expressed by a vector X which is represented by the following equation (3) and has a one-dimensional coordinate of each part as an element. In the following explanation, an underlined character indicates a vector. EQU X=(x1, x2, . . . , xi, . . . , xn) (3)
The spectral method aims at obtaining the placement of parts, namely calculating the vector X, in such a way that the circuit has the shortest possible connection line length. The positions of parts are normally expressed by natural numbers, but an element xi of the vector X corresponding to the position of each part can be assumed to be a real number. This indicates that parts can be located at the same position and the resultant placement may be impractical. However, the element xi can be a real number to easily obtain a model.
Assume that weight aij is assigned corresponding to the importance of a connection line between a part i and a part j. In this case, the total circuit connection line length minimization problem is equivalent to the problem of minimizing the value of the following equation (4). ##EQU1## On the other hand, the following equation (6) is expressed based on a matrix [M] containing the values i and j (1.ltoreq.i.ltoreq.n, 1.ltoreq.j.ltoreq.n) and the equation (3) above. In the following explanation, a character enclosed by `[` and `]` indicates a matrix. ##EQU2## where vector X.sup.T indicates a transposed vector X.
When the right-hand-side of the equation (6) is compared with the equation (4), the connection line length for the parts i and j is squared in the equation (6). In consideration of this difference, the circuit connection line length minimization problem is solved as a problem of computing the vector X for minimizing the equation (6) in the spectral method.
Assuming that an eigenvalue of the matrix [M] is .lambda. and the proper vector for the eigenvalue .lambda. is X, the following equation (7) is expressed. EQU [M]X=.lambda.X (7)
By multiplying each item by X.sup.T from the left to the right in each side, the following equation (8) is expressed. EQU X.sup.T [M]X=X.sup.T .lambda.X=.lambda.X.sup.T X=.lambda. (8)
Therefore, to compute the vector X or minimizing the equation (6), the minimum eigenvalue .lambda.min for the matrix [M] and other than 0 is first computed, then the eigenvector Xmin for the minimum eigenvalue .lambda.min is computed, and the result is set as a vector X.
Thus, the vector X for minimizing the equation (6) is computed. Since the value obtained by squaring the connection line length for the parts i and j is used as described above, computing the vector X for minimizing the equation (6) does not refer to minimizing the total circuit connection line length when the squared value is used as it is.
In the spectral method, using the predetermined weight aij of the connection line between the part i and the part j and the initial connection line lengths xi and xj between the parts i and j according to the equation (9) obtained from the equations (4) and (6), the element value aij' of the matrix [M] is computed. EQU aij.vertline.xi-xj.vertline.=aij'(xi-xj).sup.2
.thrfore. EQU aij'=aij/.vertline.xi-xj.vertline. (9)
Using the matrix [M] determined from the element value aij', the minimum eigenvalue .lambda.min other than 0 for the matrix [M] is computed, and the eigenvector Xmin for the minimum eigenvalue .lambda.min is computed as the vector X for minimizing the equation (6).
A new element value aij' of the matrix [M] is computed using new connection line lengths xi and xj between the parts i and j provided by the computed vector X and the predetermined weight aij of the connection line between the parts i and j. Based on the computed value, a subsequent vector X is computed. Thus, the processes are repeated.
In the spectral method, the placement of parts with which the total circuit connection line length can be the optimum and minimum value in approximation, that is, the vector X, is computed by repeating the above described matrix operations.
In the spectral method, it is required to compute the minimum eigenvalue .lambda.min other than 0 and a corresponding eigenvector Xmin. If the number of parts increases and the number of dimensions of a matrix also increases, the process time is extended and the computation precision is dramatically lowered. Therefore, a method of reducing the number of dimensions of a matrix has recently been suggested by clustering parts originally related to each other into one part group.
However, since an integer indicating the position of parts is extended to a real number to perform the total circuit connection line length minimizing process in the spectral method, it is not certain that the minimization can be realized for the optimum total circuit connection line length.
When the number of parts is very large as in the case of recent semiconductor integrated circuits, the computation of a proper vector requires a long time with an increase in computation error.
Furthermore, in the spectral method, a nonlinear converting process is performed between the actual connection line length and a squared connection line length as described above using the equation (9). Therefore, there is the problem that the solution space is not smooth as shown in FIG. 1, and that there is a strong probability that the placement of the parts can enter a status of a local optimum solution.
The problems with the above described SA method and spectral method are not limited to the total circuit connection line length minimization problem. For example, a schedule optimization problem occurring when the optimum scheduling is performed between, for example, a plurality of actions, can also be considered.